
"""
112. 路径总和
"""
from typing import Optional

from com.siyuan.TreeNode import TreeNode


class Solution:

    def __init__(self):
        self.sum1 = 0
        self.res = False

    def hasPathSum1(self, root: Optional[TreeNode], targetSum: int) -> bool:
        """
         解法1，分解二叉树
         函数定义，输入参数为二叉树根节点和目标值，输出：存在根节点到叶子节点 的路径和为target
        """
        if not root:
            return False

        # 判断当前节点是否等于目标值（前提是叶子结点）
        if not root.left and not root.right:
            return root.val == targetSum

        # 遍历左右子树
        return self.hasPathSum1(root.left, targetSum - root.val) or self.hasPathSum1(root.right, targetSum - root.val)

    def hasPathSum2(self, root: Optional[TreeNode], targetSum: int) -> bool:
        """
         解法2，遍历二叉树
         维护1个外部变量，表示从根节点到当前节点值之和
        """
        if not root:
            return False
        self.traverse(root, targetSum)
        return self.res

    '''遍历二叉树'''
    def traverse(self, root: Optional[TreeNode], targetSum: int):
        if not root:
            return
        self.sum1 += root.val
        if not root.left and not root.right and self.sum1 == targetSum:
            self.res = True
            return
        # 前序位置
        self.traverse(root.left, targetSum)
        # 中序位置
        self.traverse(root.right, targetSum)
        # 后序位置
        self.sum1 -= root.val
